package com.ls.que111_115;

/**
 * @author ：ls
 * @date ：2022/3/30 17:47
 * @description：...
 */
public class NumDistinct {
    public int numDistinct(String s, String t) {
        char[] s1 = s.toCharArray();
        char[] s2 = t.toCharArray();

        if (s1.length < s2.length)
            return 0;

        int[][] dp = new int[s1.length+1][s2.length+1];
        int i=0,j=0;
        for (i=0;i<=s1.length;i++){
            dp[i][s2.length] = 1;
        }

        for (i=0; i<s2.length;i++){
            dp[s1.length][i] = 0;
        }

        for (i=s1.length-1; i>=0; i--){
            for (j=s2.length-1; j>=0; j--){
                if (s1[i] == s2[j]){
                    dp[i][j] = dp[i+1][j+1] + dp[i+1][j];
                }else {
                    dp[i][j] = dp[i+1][j];
                }
            }
        }
        return dp[0][0];
    }
}
